模拟赛题解/2025.9.3 模拟赛

T1-那头与出题（data）

题面

那头在出题时发现他不会写一道题的 generator，需要你进行帮助。

我们称一个对无限大网格图的黑白染色方案是合法的当且仅当所有黑色点四联通，所有白色点也四联通。

具体的，我们在 $(x_1,y_1)$ 与 $(x_2,y_2)$ 之间连边当且仅当 $|x_1-x_2|+|y_1-y_2|=1$ 且两个点颜色相同，如果得到的图的联通块数为 $1$ 或 $2$，那么染色方案合法，否则不合法。

初始时所有点都是白色的，你需要维护 $q$ 次修改。

第 $i$ 次修改有两个参数 $x_i,y_i$ 表示尝试把 $(x_i,y_i)$ 涂黑（保证这个点当前是白色)。如果涂黑后染色依然合法则执行该操作，否则放弃该操作。

你需要求出每次操作是否被执行。

$1\leq q,x_i,y_i\leq3\times10^5$。

题解

每次新加入的点是否能让黑色保持联通是易于判断的，判断新加入的黑点上下左右是否有其他黑点即可。

考虑如何判定白色能否保持联通，注意到只需要考虑新加入点周围 $3\times3$ 九宫格内的情况即可，九宫格外的白点并不会受到影响。

因此每次检查新加入一个点后九宫格内黑色白色的连通性即可。

T2-那头与分值（score）

题面

那头需要完成 $n$ 道题目，第 $i$ 道题目难度为 $a_i$。那头有一个智慧值 $X$，他完成所有题目需要 $(a_1+X)\oplus(a_2+X)\oplus\cdots\oplus(a_n+X)$ 的时间。

那头会 $q$ 次调整自己的智慧值，你需要每次告诉他完成所有题目会完成的时间。即给定 $x_i$，你需要求出 $(a_1+x_i)\oplus(a_2+x_i)\oplus\cdots\oplus(a_n+x_i)$ 的值。那头不希望等待，所以本题部分测试点要求强制在线。

$n\leq2\times10^5,q\leq5\times10^5,t\in\{0,1\},a_i,x_i'<2^{60}$。

题解

考虑决策答案每一位是 $0$ 还是 $1$。对于第 $i$ 位，需要查询有多少个 $i$ 满足 $a_i+X$ 的第 $i$ 位为 $1$。可以转化为统计进位次数。这相当于查询 $a_i\&(2^i−1)$ 在一个区间内的值的个数， 可以预处理 $b_{k,i}=a_i\&(2^k−1)$ 并对 $b_k$ 排序然后二分查询。

复杂度 $O((n+q)\log n\log V)$， 期望得分 $60$ 分。

尝试优化以上算法。预处理部分容易优化，可以通过归并做到 $O(n\log V )$（但这部分 不是瓶颈，不优化也可以通过）。难点在于优化询问。如果允许离线，可以对于每个 $x$ 也预处理 $x\&(2k−1)$ 并排序，然后双指针扫描回答询问，复杂度 $O((n+q)\log V)$，期望得分 $85$ 分。

如果要求强制在线，我们无法对 $x_i$ 排序预处理，所以只能尝试通过本次询问第 $k$ 位 的结果推出 $k+1$ 位的结果。考虑一次询问是要求 $b_{k,i}<2^{k+1}−x\&(2^{k+1} − 1)$ 的最大的 $i$ 的位置。当 $k\leftarrow k+1$，式子左侧的值要么不变，要么增加 $2^k$。这启发我们预处理 $c_{k,i,0}=\max{x|b_{k+1,x}\leq b{k,i}}$，$c_{k,i,1}=\max{x|b_{k+1,x}\leq b_{k,i}+2^k}$ 辅助转移。如果可以得到以上数组，每次 $k\leftarrow k+1$ 可以直接通过调用 $c$ 完成。$c$ 可以和 $b$ 一起在归并时求出。

复杂度 $O((n+q)\log V)$，期望得分 $100$ 分。

T3-那头与观测（observation）

题面

那头住在一棵 $n$ 个点的树上。

那头在树的每个节点上都放置了一个头。其中 $i$ 号节点上的头为 $i$ 号头，其高度为 $i$。对于整数 $1\leq h\leq n$，称两个不同的头在视线高度为 $h$ 时可以互相望见当且仅当：

• 两个头的高度都 $\geq h$。
• 两个头所在节点的简单路径上没有其他头或其他头的高度都 $<h$。

对于每个整数 $1\leq h\leq n$，求有多少个有序三元组 $(i,j,k)$ 满足：

• $i,j,k$ 互不相同。
• 在视线高度为 $h$ 时，$i$ 号头和 $j$ 号头可以互相望见且 $j$ 号头和 $k$ 号头可以互相望见。

$2\leq n\leq10^5$。

题解

考虑按编号从小到大删点。时刻维护一个 $n−h+1$ 个点的无向图 $G$。$G$ 中 $(u,v)$ 有边当且仅当 $u,v$ 在视线高度为 $h$ 时可以互相望见。令 $u$ 在 $G$ 中的度数为 $d_u$，则答案为 $\sum_{u} d_u(d_u−1)$。

直接建边边数过多，且维护图并不方便。考虑建一些虚点让图变成一棵树。删点开始前，对于原树上的一条边 $(u_i,v_i)$，在新树上连接 $(u_i,n+i)$ 和 $(v_i,n+i)$。设编号 $>n$ 的为白点，$\leq n$ 的为黑点。删除 $u$ 相当于把 $u$ 的子白点与它的父白点合并，可以使用并查集维 护。容易发现新树上的点是黑白相间的，且对于 $G$ 中的边 $(u,v)$，新树上一定存在恰好一个白点 $x$ 满足 $(u,x),(x,v)$ 这两条边在新树上存在。为了方便，以 $n$ 作为新树的根，这样根一定不会被删掉。

考虑如何算答案。把三元组 $(a,b,c)$ 变成 $(a,x,b,y,c)$（$x,y$ 是白点）。令 $f_u$ 为白点 $u$ 的 黑儿子个数，分情况讨论：

• 当 $x=y$ 时，相当于在 $x$ 的邻点中选 $a,b,c$，$x$ 的邻点有 $f_x+1$ 个（因为要算上他的 父亲）。故对答案的贡献为 $\sum_{x\in W}(f_x+1)f_x(f_x−1)$，其中 $W$ 为白点点集。
• 当 $x\not=y$ 且 $x,y$ 为 $b$ 的儿子时，相当于分别在 $x,y$ 的儿子中选 $a,c$，贡献为 $\sum_{b\in B}\sum_{x,y\in son_b,x\not=y}f_xf_y$。 即 $\sum_{b\in B}\left(\sum_{x\in son_b}f_x\right)^2−\sum_{x\in son_b}f^2_x$。其中 $son_u$ 为 $u$ 的儿子集合，$B$ 为黑点点集。
• 当 $x$ 为 $b$ 父亲，$y$ 为 $b$ 儿子时，相当于在 $x$ 的邻点中选 $a$，在 $x$ 的儿子中选 $b\not=a$，$y$ 中选 $c$。答案为 $\sum_{x\in B}2(f_x + 1 − 1) \sum_{b\in son_x}\sum_{y\in son_b}f_y$。乘二是因为三元组是有序的，$(a,c),(c,a)$ 应该被算两遍。

每次删除一个点会影响其下一级儿子与上三级父亲。因此对于一个白点维护其下一级， 下三级信息，对于一个黑点维护其下两级信息即可。具体地，可以令 $g_u=\sum_{v\in son_u}f_v$，$h_u=\sum_{v\in son_u}g_v$。删除 $u$ 的复杂度为并查集的复杂度加上遍历 $u$ 的儿子的复杂度。

T4-那头与方程（equation）

题面

给定正整数 $n,a,b,c,d$。

请判断是否存在非负整数 $x$，使得对于所有 $k=0,1,\cdots,n-1$，都有 $x\equiv a+kb(\bmod c+kd)$。如果存在，请输出所有满足条件的 $x$ 中最小的一个对 $998244353$ 取模的结果；如果不存在，请输出 $-1$。

$2\leq n\leq 10^6,1\leq a,b,c,d\leq 2\times10^6$。

题解

先考虑 $\gcd (c,d)=1$ 的情况。

将式子两端同乘 $d$，得到 $xd\equiv ad+bdk (\bmod c + dk)\rightarrow xd\equiv ad − bc (\bmod c + dk)$。

此时题目条件为 $xd\equiv ad − bc (\bmod M)$，其中 $M = \text{lcm}^{n−1}_{i=0}(c+d_i)$。

即找到一个最小的 $y$ 使得 $S=My+((ad−bc)\bmod M),S\geq 0,S\equiv0(\bmod d)$，则此时 $x=\frac{S}{d}$。

我们尝试将 $M$ 的质因子筛出来。 若 $\gcd (c+d_i,c+d_j)\not=1(i<j)$，则存在 $p,p|(c+d_i),p|(c+d_j)$，则 $p|d(j−i)$。

若 $p|d$，则根据 $p|(c+d_i)$ 显然有 $p|c$，与条件 $\gcd(c,d)=1$ 矛盾。

所以 $p|(j−i)$，即每个 $c+dk$ 仅存在 $\leq n$ 的质因子，以及有可能含有唯一的 $>n$ 的质因子。

对于 $\leq n$ 的质因子 $p$，我们只需找到最小的 $k$ 使得 $p|(c+dk)$（这个可以 $\text{exgcd}$ ），然后任意满足 $p|(c+dx)$ 的 $x$ 一定可以表示为 $x=k+p·t$。

求出了 $M$ 的质因子表示后，因为有 $\gcd(M,d)=1$，我们就可以枚举 $y\in [0,d]$ 来试了。这里需要分讨 $M$ 的大小以及 $ad−bc$ 的正负性，具体可详见 std。

最后的问题是，$\gcd (c,d)\not=1$ 怎么办？令 $\gcd(c,d)=s$，容易发现 $b\equiv0(\bmod s)$，这是判断是否有解的充要条件。

然后可以求得子问题 $x'\equiv \lfloor \frac{a}{s}\rfloor+k·\frac{b}{s}(\bmod\frac{c}{s}+k·\frac{d}{s})$，最终答案为 $x=x'·s+(a\bmod s)$。